package DataStr.ex01;

import java.util.LinkedList;

public class ex05 {
    //定义链表节点类
    static class Node{
        int a;
        Node next;

        Node(int a){
            this.a=a;
            this.next=null;//初始化next为null
        }
    }
    //定义链表类
public static class LinkList{
        public Node move(Node head){
            Node n1=new Node(0);//头结点
            Node n2=new Node(0);//头结点
            Node a=n1;//指向n1的最后一个节点
            Node b=n2;//指向n2的最后一个节点
            Node current=head;//从链表头开始遍历
                while(current!=null){
                    if(current.a<0){
                        a.next=current;//将负数连接到负数链表
                        a=a.next;//移动负数链表的指针
                    }else{
                        b.next=current;
                        b=b.next;
                    }
                    current=current.next;
                }
                //结束正数链表
            b.next=null;
                //连接负数链表和正数链表
            a.next=n2.next;
            //返回新链表的头
            return n1.next;
                }
            }
            public static void main(String[]args){
             Node head=new Node(1);
                 head.next=new Node(2);
                 head.next.next=new Node(-1);
                 head.next.next.next=new Node(-2);
                 head.next.next.next.next=new Node(3);
                 head.next.next.next.next.next=new Node(-3);
                 head.next.next.next.next.next.next=new Node(4);

                 LinkList lk=new LinkList();
                 Node newHead=lk.move(head);//调用move方法并返回新头结点

                 while(newHead!=null){
                     System.out.print(newHead.a+" ");
                     newHead=newHead.next;
                 }
             }
}


